package srcInterviewPrep;

public final class SearchInRotatedArray
{
    public static int FindInRotatedArray(int a[], int x)
    {
        int offset = GetPositionOfSmallestElement(a) + 1;
        
        int start = 0;
        int end = a.length - 1;
        int n = a.length;
        
        while(end > start)
        {
            int mid = (start + end)/2;
            
            int midPos = (mid + offset) % n;
            
            if (x == a[midPos])
            {
                return midPos;
            }
            
            if (x < a[midPos])
            {
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }       
        
        return (end + offset) % n;
    }
    
    private static int GetPositionOfSmallestElement(int a[])
    {
        int start = 0;
        int n = a.length;
        int end = n - 1;
        
        while(start < end)
        {
            int mid = (start + end)/2;
            
            if (a[start] < a[mid])
            {
                start = mid + 1;
            }
            else
            {
                end = mid;
            }
        }
        
        return end;
    }
}
    
